An image to be processed may be presented in a variety of ways. The most "natural" of these is to represent one or more intrinsic properties of the image (such as surface brightness, color, or range) in an ordered array or map whose cells correspond to the spatial locations of the image points. Such a map is often called an "iconic" image. An example of an iconic image is the representation of images on a television screen. An alternative image representation, often called a "symbolic" image, results when features of the image are represented by symbols which are stored in linked list or similar data structure. A chain-coded representation of edges is an example of a symbolic representation.
Since an iconic image is spatially indexed, the whole image, or whole subregions of the image, must usually be processed during each operation, and massively parallel processing is required for real-time operation. Serial computer image-processing techniques typically attempt to reduce the image to a symbolic representation as rapidly as possible to enhance the efficiency of serial processing. While this data compression brings many image processing operations within the capabilities of ordinary serial computers, it makes many other operations more difficult, such as subtracting one image from another.
Parallel processors are ideally suited to the early stages of image processing, where spatial and temporal features have not yet been discovered. They lend themselves to processing strategies based on multi-resolution (pyramid) representations, and facilitate relaxation techniques for which a spatially ordered representation is most natural and efficient. Unfortunately, true multi-stage parallel processing is prohibitively expensive for images of useful size.
As will appear, the processor of the invention is intended to perform transformations on images to extract features similar to those in the primal sketch disclosed in D. Marr, "Early Processing of Visual Information", Phil. Trans. Royal Society, B.275, 1976. Prior art processors of interest include the PUMPS system described in F. A. Briggs, K. S. Fu, K. Hwang, and B. W. Wah, "PUMPS Architecture for Pattern Analysis and Image Database Management", IEEE Trans. Computers C-31 10, Oct. 1982, pp. 969-983. The PUMPS system is an example of a multi-user system in which various task processing units are allocated from a pool. Each processor is specialized for a particular purpose, and images are transformed by passing them through a sequence of different processors.
Other prior art systems have components that perform some of the functions of the processor of the invention. However, these systems usually operate on a single image at a time. For example, the PICAP II system, disclosed in D. Antonsson, B. Gudmundsson, T. Hedblom, B. Kruse, A. Linge, P. Lord, and T. Ohlsson, "PICAP--A System Approach to Image Processing", IEEE Trans. Computers, C-31 10, Oct. 1982, pp. 997-1000, has a filter processor, FLIP, that performs some of the operations of a stage in the processor of the invention. The system also has other processors that are specialized for operations such as image segmentation. Further, the FLIP system disclosed in X. Luetjen, X. Gemmar, and X. Ischem, "FLIP: A Flexible Multi Processor System for Image Processing", Proc. Fifth International Conference on Pattern Recognition, Miami, Fla., 1980 is similar to the processor of the invention in that, in common with the latter, it has a number of identical processors, but the FLIP system usually uses these processors in parallel on sub- images of the same image instead of on successive versions of complete images. The FLIP system also allows greater flexibility in the connections between its processors. As will be explained, in the system of the invention processors are normally connected only to their immediate predecessors and successors, although "wildcard" busses which are provided allow selective but limited connections between arbitrary stages. The FLIP system, on the other hand, provides connections between all processors, allowing the processors to be arranged to suit each particular task.
Other special processors for image processing include the massively parallel processor, the MPP system disclosed in J. L. Potter, "Image Processing on the Massively Parallel Processor", IEEE Computer Magazine 16, Jan. 1983, pp. 62-67, and the ZMOB system, disclosed in T. Kushner, A. Y. Wu and A. Rosenfeld, "Imaging Processing on ZMOB", IEEE Trans. Computers, C-31 10, Oct. 1982, pp 943-951, which is a more general parallel processor but which has been studied extensively with regard to its abilities to perform image processing tasks. The MPP system has 16K processors, and is a true parallel processor. Experience with the processor is limited, but a major difficulty appears to be the problem of transferring the data to each individual processor, and getting the results out of the machine. The MPP system does not have a true neighborhood operator, although each processor can be connected to four of its neighbors and use the pixel values there to compute the result. It is not clear that the MPP processor has any advantage over pipelined systems, because the images are usually obtained from an imaging system or storage medium in a stream, and sent to successive processors in the same fashion.
The ZMOB system consists of 256 processors connected by a ring-shaped high speed communications system. The communications link operates fast enough to make each processor appear to be connected to all others. Each processsor is a general-purpose eight-bit microcomputer, with 64K bytes of memory. Thus, many different computations can be performed at the same time, either on the same or different data. For image-processing applications, images are usually broken into parts, each of which is sent to a different processor. Many operations require interaction between the parts, especially when neighborhood operations are performed. This gives rise to the need for communications between processors. Given that the communications link is much faster than the cycle time of the processors, there is very little overhead involved. However, upgrading the processors might cause data transmissions to become significant.
Other prior art of possible interest is the digital image processing apparatus disclosed in U.S. Pat. No. 4,330,833 (Pratt et al).